
from btree import Btree
class BtreeVisitor:
    def __init__(self, btree):
        self.__btree = btree

    def visitNode(self):
        pass

    def visit(self):
        pass

    def getBtree(self):
        return self.__btree

class BtreeLayerVisitor(BtreeVisitor):

    EndOfLayerSymbol = None
    @staticmethod
    def isEndOfLayer(obj):
        return obj is None

    class IResult:
        def begin(self, root):
            return True
        def nodeBegin(self, node):
            return True
        def cell(self, node, cell):
            return True
        def nodeEnd(self, node):
            return True
        def layerEnd(self):
            return True
        def end(self, root):
            return True

        def getFinal(self):
            pass

    class DefaultResult(IResult):
        def __init__(self):
            self.__result = []
            
        def nodeBegin(self, node):
            self.__result.append("[")
            return True
        def cell(self, node, cell):
            #self.__result.append("(%s:%d), " % (cell.getKey(), cell.getData()))
            self.__result.append("(%s:%d), " % (cell.getKey(), ord(cell.getKey()[0])))
            return True
        def nodeEnd(self, node):
            self.__result.append("] #  ")
            return True
        def layerEnd(self):
            self.__result.append("\n")
            return True

        def getFinal(self):
            return "".join(self.__result)

    def __init__(self, btree, result = None):
        BtreeVisitor.__init__(self, btree)
        self.__fifo = []
        self.__result = result is not None and result or BtreeLayerVisitor.DefaultResult()

    def __visit(self):
        while len(self.__fifo) > 0 :  
            node = self.__fifo.pop(0)
            if not BtreeLayerVisitor.isEndOfLayer(node) :
                self.visitNode(node)
            else:
                if not self.__result.layerEnd():
                    return 
                if len(self.__fifo) >= 1:
                    self.__fifo.append(BtreeLayerVisitor.EndOfLayerSymbol)
                else :
                    pass
            #end if
        #end while
    #end def

    def visitNode(self, node):
        if not self.__result.nodeBegin(node):
            return 

        # all cell add to queue
        for c in node.getCells():
            if not self.__result.cell(node, c) :
                return 
            if c.getNode() is not None:
                self.__fifo.append(c.getNode())

        # biggestNode to queue
        if node.getBiggestNode() is not None:
            self.__fifo.append(node.getBiggestNode())

        if not self.__result.nodeEnd(node):
            return 

    def visit(self):
        if self.getBtree() is not None:
            root = self.getBtree().getRoot()
            if root is not None:
                if not self.__result.begin(root):
                    return 

                self.__fifo.append(root)
                self.__fifo.append(BtreeLayerVisitor.EndOfLayerSymbol)
                self.__visit()

                if not self.__result.end(root):
                    return 
        #end if
        return self

    def getResult(self):
        return self.__result
    

from util import Util
class PtrResult(BtreeLayerVisitor.IResult):
    def __init__(self):
        self.__result = []

    def nodeBegin(self, node):
        self.__result.append("%x[" % Util.getId(node))
        return True

    def cell(self, node, cell):
        self.__result.append("(%x|'%s'), " % (Util.getId(cell.getNode()), cell.getKey()))
        #self.__result.append("(0x%x|'%s':%d), " % (Util.getId(cell.getNode()), cell.getKey(), cell.getData()))
        return True

    def nodeEnd(self, node):
        if node.getBiggestNode() is None:
            self.__result.append("] # ")
        else:
            self.__result.append("] %x # " % Util.getId(node.getBiggestNode()))
        return True

    def layerEnd(self):
        self.__result.append("\n")
        return True

    def getFinal(self):
        return "".join(self.__result)

from util import Util
class MaxResult(BtreeLayerVisitor.IResult):
    MinKey = None
    def __init__(self):
        self.__result = MaxResult.MinKey

    def cell(self, node, cell):
        if self.__result < cell.getKey():
            self.__result = cell.getKey()
        return True

    def getFinal(self):
        return self.__result

class MinResult(BtreeLayerVisitor.IResult):
    MaxKey = chr(127)
    def __init__(self):
        self.__result = MinResult.MaxKey

    def cell(self, node, cell):
        if self.__result > cell.getKey():
            self.__result = cell.getKey()
        return True
    def getFinal(self):
        return self.__result

if __name__ == "__main__":
    def createBtree():
        btree = Btree()
        btree.insert("M")
        btree.insert("N")
        btree.insert("L")
        btree.insert("O")
        btree.insert("W")
        btree.insert("A")
        return btree

    print "Walk:", BtreeLayerVisitor(createBtree(), PtrResult()).visit().getResult().getFinal()
    print "Max:", BtreeLayerVisitor(createBtree(), MaxResult()).visit().getResult().getFinal()
    print "Min:" , BtreeLayerVisitor(createBtree(), MinResult()).visit().getResult().getFinal()
